#ifndef HEAP_H
#define HEAP_H

template <class T>
class heap
{
private:
	T *p;
	int maxSize;
	int size;
	bool dominate(T x, T y);
public:
	heap(int maxSize);
	~heap();
	bool isEmpty(){return size==0;}
	void print();
	void insert(T x);
	void remove();
	T top(){return p[0];};

};

template <class T>
heap<T>::heap(int maxSize)
{
	p = new T[size];
	if(p==NULL){
		cout<<"Lack of Memory! "<<endl;
		exit(1);
	}
	this->maxSize = maxSize;
	size = 0;
}

template <class T>
heap<T>::~heap()
{
	delete []p;
}

template <class T>
bool heap<T>::dominate(T x, T y)
{
	if(x.minDis < y.minDis) return true;
	else return false;
}

template <class T>
void heap<T>::insert(T x)
{
	size++;
	if (size > maxSize){
		cout<<"Out of Bound!";
		exit(1);
	}
	
	int i = size-1;
	int parent = (i-1)/2;
	T temp = x;
	while(i>0 && dominate(temp,p[parent])){
		p[i] = p[parent];
		i = parent;
		parent = (i-1)/2;
	}
	p[i] = temp;
}

template <class T>
void heap<T>::remove()
{
	T temp = p[size-1];
	size--;
	int i = 1, parent = 0;
	while(i <= size-1){
		if(i+1 <= size-1 && p[i] < p[i+1]) i++;
		if(temp < p[i]) p[parent] = p[i];
		else break;
		parent = i;
		i = 2*i+1;
	}
	p[parent] = temp;
}

template <class T>
void heap<T>::print()
{
	for(int i=0;i<size;i++)
		cout<<p[i]<<" ";
	cout<<endl;
}

#endif